home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 2 / Amiga Tools 2.iso / tools / vim / src / regexp.c < prev    next >
C/C++ Source or Header  |  1995-03-09  |  40KB  |  1,678 lines
  1. /* vi:ts=4:sw=4
  2.  * NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE
  3.  *
  4.  * This is NOT the original regular expression code as written by
  5.  * Henry Spencer. This code has been modified specifically for use
  6.  * with the VIM editor, and should not be used apart from compiling
  7.  * VIM. If you want a good regular expression library, get the
  8.  * original code. The copyright notice that follows is from the
  9.  * original.
  10.  *
  11.  * NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE
  12.  *
  13.  *
  14.  * regcomp and regexec -- regsub and regerror are elsewhere
  15.  *
  16.  *        Copyright (c) 1986 by University of Toronto.
  17.  *        Written by Henry Spencer.  Not derived from licensed software.
  18.  *
  19.  *        Permission is granted to anyone to use this software for any
  20.  *        purpose on any computer system, and to redistribute it freely,
  21.  *        subject to the following restrictions:
  22.  *
  23.  *        1. The author is not responsible for the consequences of use of
  24.  *                this software, no matter how awful, even if they arise
  25.  *                from defects in it.
  26.  *
  27.  *        2. The origin of this software must not be misrepresented, either
  28.  *                by explicit claim or by omission.
  29.  *
  30.  *        3. Altered versions must be plainly marked as such, and must not
  31.  *                be misrepresented as being the original software.
  32.  *
  33.  * Beware that some of this code is subtly aware of the way operator
  34.  * precedence is structured in regular expressions.  Serious changes in
  35.  * regular-expression syntax might require a total rethink.
  36.  *
  37.  * $Log:        regexp.c,v $
  38.  * Revision 1.2  88/04/28  08:09:45  tony
  39.  * First modification of the regexp library. Added an external variable
  40.  * 'reg_ic' which can be set to indicate that case should be ignored.
  41.  * Added a new parameter to regexec() to indicate that the given string
  42.  * comes from the beginning of a line and is thus eligible to match
  43.  * 'beginning-of-line'.
  44.  *
  45.  * Revisions by Olaf 'Rhialto' Seibert, rhialto@cs.kun.nl:
  46.  * Changes for vi: (the semantics of several things were rather different)
  47.  * - Added lexical analyzer, because in vi magicness of characters
  48.  *   is rather difficult, and may change over time.
  49.  * - Added support for \< \> \1-\9 and ~
  50.  * - Left some magic stuff in, but only backslashed: \| \+
  51.  * - * and \+ still work after \) even though they shouldn't.
  52.  */
  53. #include "vim.h"
  54. #include "globals.h"
  55. #include "proto.h"
  56. #undef DEBUG
  57.  
  58. #include <stdio.h>
  59. #include "regexp.h"
  60. #include "regmagic.h"
  61. #include "param.h"
  62.  
  63. /*
  64.  * The "internal use only" fields in regexp.h are present to pass info from
  65.  * compile to execute that permits the execute phase to run lots faster on
  66.  * simple cases.  They are:
  67.  *
  68.  * regstart     char that must begin a match; '\0' if none obvious
  69.  * reganch        is the match anchored (at beginning-of-line only)?
  70.  * regmust        string (pointer into program) that match must include, or NULL
  71.  * regmlen        length of regmust string
  72.  *
  73.  * Regstart and reganch permit very fast decisions on suitable starting points
  74.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  75.  * of lines that cannot possibly match.  The regmust tests are costly enough
  76.  * that regcomp() supplies a regmust only if the r.e. contains something
  77.  * potentially expensive (at present, the only such thing detected is * or +
  78.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  79.  * supplied because the test in regexec() needs it and regcomp() is computing
  80.  * it anyway.
  81.  */
  82.  
  83. /*
  84.  * Structure for regexp "program".    This is essentially a linear encoding
  85.  * of a nondeterministic finite-state machine (aka syntax charts or
  86.  * "railroad normal form" in parsing technology).  Each node is an opcode
  87.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  88.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  89.  * a BRANCH on both ends of it is connecting two alternatives.    (Here we
  90.  * have one of the subtle syntax dependencies:    an individual BRANCH (as
  91.  * opposed to a collection of them) is never concatenated with anything
  92.  * because of operator precedence.)  The operand of some types of node is
  93.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  94.  * particular, the operand of a BRANCH node is the first node of the branch.
  95.  * (NB this is *not* a tree structure:    the tail of the branch connects
  96.  * to the thing following the set of BRANCHes.)  The opcodes are:
  97.  */
  98.  
  99. /* definition    number               opnd?    meaning */
  100. #define END     0                /* no    End of program. */
  101. #define BOL     1                /* no    Match "" at beginning of line. */
  102. #define EOL     2                /* no    Match "" at end of line. */
  103. #define ANY     3                /* no    Match any one character. */
  104. #define ANYOF    4                /* str    Match any character in this string. */
  105. #define ANYBUT    5                /* str    Match any character not in this
  106.                                  *        string. */
  107. #define BRANCH    6                /* node Match this alternative, or the
  108.                                  *        next... */
  109. #define BACK    7                /* no    Match "", "next" ptr points backward. */
  110. #define EXACTLY 8                /* str    Match this string. */
  111. #define NOTHING 9                /* no    Match empty string. */
  112. #define STAR    10                /* node Match this (simple) thing 0 or more
  113.                                  *        times. */
  114. #define PLUS    11                /* node Match this (simple) thing 1 or more
  115.                                  *        times. */
  116. #define BOW        12                /* no    Match "" after [^a-zA-Z0-9_] */
  117. #define EOW        13                /* no    Match "" at    [^a-zA-Z0-9_] */
  118. #define MOPEN    20                /* no    Mark this point in input as start of
  119.                                  *        #n. */
  120.  /* MOPEN+1 is number 1, etc. */
  121. #define MCLOSE    30                /* no    Analogous to MOPEN. */
  122. #define BACKREF    40                /* node Match same string again \1-\9 */
  123.  
  124. #define Magic(x)    ((x)|('\\'<<8))
  125.  
  126. /*
  127.  * Opcode notes:
  128.  *
  129.  * BRANCH        The set of branches constituting a single choice are hooked
  130.  *                together with their "next" pointers, since precedence prevents
  131.  *                anything being concatenated to any individual branch.  The
  132.  *                "next" pointer of the last BRANCH in a choice points to the
  133.  *                thing following the whole choice.  This is also where the
  134.  *                final "next" pointer of each individual branch points; each
  135.  *                branch starts with the operand node of a BRANCH node.
  136.  *
  137.  * BACK         Normal "next" pointers all implicitly point forward; BACK
  138.  *                exists to make loop structures possible.
  139.  *
  140.  * STAR,PLUS    '=', and complex '*' and '+', are implemented as circular
  141.  *                BRANCH structures using BACK.  Simple cases (one character
  142.  *                per match) are implemented with STAR and PLUS for speed
  143.  *                and to minimize recursive plunges.
  144.  *
  145.  * MOPEN,MCLOSE    ...are numbered at compile time.
  146.  */
  147.  
  148. /*
  149.  * A node is one char of opcode followed by two chars of "next" pointer.
  150.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  151.  * value is a positive offset from the opcode of the node containing it.
  152.  * An operand, if any, simply follows the node.  (Note that much of the
  153.  * code generation knows about this implicit relationship.)
  154.  *
  155.  * Using two bytes for the "next" pointer is vast overkill for most things,
  156.  * but allows patterns to get big without disasters.
  157.  */
  158. #define OP(p)    (*(p))
  159. #define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  160. #define OPERAND(p)        ((p) + 3)
  161.  
  162. /*
  163.  * See regmagic.h for one further detail of program structure.
  164.  */
  165.  
  166.  
  167. /*
  168.  * Utility definitions.
  169.  */
  170. #ifndef CHARBITS
  171. #define UCHARAT(p)        ((int)*(unsigned char *)(p))
  172. #else
  173. #define UCHARAT(p)        ((int)*(p)&CHARBITS)
  174. #endif
  175.  
  176. #define EMSG_RETURN(m) { emsg(m); return NULL; }
  177.  
  178. static int ismult __ARGS((int));
  179.  
  180.     static int
  181. ismult(c)
  182.     int c;
  183. {
  184.     return (c == Magic('*') || c == Magic('+') || c == Magic('='));
  185. }
  186.  
  187. /*
  188.  * Flags to be passed up and down.
  189.  */
  190. #define HASWIDTH        01        /* Known never to match null string. */
  191. #define SIMPLE            02        /* Simple enough to be STAR/PLUS operand. */
  192. #define SPSTART         04        /* Starts with * or +. */
  193. #define WORST            0        /* Worst case. */
  194.  
  195. /*
  196.  * The following allows empty REs, meaning "the same as the previous RE".
  197.  * per the ed(1) manual.
  198.  */
  199. /* #define EMPTY_RE */            /* this is done outside of regexp */
  200. #ifdef EMPTY_RE
  201. char_u           *reg_prev_re;
  202. #endif
  203.  
  204. #define TILDE
  205. #ifdef TILDE
  206. char_u           *reg_prev_sub;
  207. #endif
  208.  
  209. /*
  210.  * This if for vi's "magic" mode. If magic is false, only ^$\ are magic.
  211.  */
  212.  
  213. int                reg_magic = 1;
  214.  
  215. /*
  216.  * Global work variables for regcomp().
  217.  */
  218.  
  219. static char_u    *regparse;    /* Input-scan pointer. */
  220. static int        regnpar;        /* () count. */
  221. static char_u     regdummy;
  222. static char_u   *regcode;        /* Code-emit pointer; ®dummy = don't. */
  223. static long     regsize;        /* Code size. */
  224. static char_u   **regendp;        /* Ditto for endp. */
  225.  
  226. /*
  227.  * META contains all characters that may be magic, except '^' and '$'.
  228.  * This depends on the configuration options TILDE, BACKREF.
  229.  * (could be done simpler for compilers that know string concatenation)
  230.  */
  231.  
  232. #ifdef TILDE
  233. # ifdef BACKREF
  234.        static char_u META[] = ".[()|=+*<>~123456789";
  235. # else
  236.        static char_u META[] = ".[()|=+*<>~";
  237. # endif
  238. #else
  239. # ifdef BACKREF
  240.        static char_u META[] = ".[()|=+*<>123456789";
  241. # else
  242.        static char_u META[] = ".[()|=+*<>";
  243. # endif
  244. #endif
  245.  
  246. /*
  247.  * Forward declarations for regcomp()'s friends.
  248.  */
  249. static void        initchr __ARGS((char_u *));
  250. static int        getchr __ARGS((void));
  251. static int        peekchr __ARGS((void));
  252. #define PeekChr() curchr    /* shortcut only when last action was peekchr() */
  253. static int         curchr;
  254. static void        skipchr __ARGS((void));
  255. static void        ungetchr __ARGS((void));
  256. static char_u    *reg __ARGS((int, int *));
  257. static char_u    *regbranch __ARGS((int *));
  258. static char_u    *regpiece __ARGS((int *));
  259. static char_u    *regatom __ARGS((int *));
  260. static char_u    *regnode __ARGS((int));
  261. static char_u    *regnext __ARGS((char_u *));
  262. static void     regc __ARGS((int));
  263. static void     unregc __ARGS((void));
  264. static void     reginsert __ARGS((int, char_u *));
  265. static void     regtail __ARGS((char_u *, char_u *));
  266. static void     regoptail __ARGS((char_u *, char_u *));
  267.  
  268. #undef STRCSPN
  269. #ifdef STRCSPN
  270. static int        strcspn __ARGS((const char_u *, const char_u *));
  271. #endif
  272.  
  273. /*
  274.  * skip past regular expression
  275.  * stop at end of 'p' of where 'dirc' is found ('/', '?', etc)
  276.  * take care of characters with a backslash in front of it
  277.  * skip strings inside [ and ].
  278.  */
  279.     char_u *
  280. skip_regexp(p, dirc)
  281.     char_u    *p;
  282.     int        dirc;
  283. {
  284.     int        in_range = FALSE;
  285.  
  286.     for (; p[0] != NUL; ++p)
  287.     {
  288.         if (p[0] == dirc && !in_range)        /* found end of regexp */
  289.             break;
  290.         if ((p[0] == '[' && p_magic) || (p[0] == '\\' && p[1] == '[' && !p_magic))
  291.         {
  292.             in_range = TRUE;
  293.             if (p[0] == '\\')
  294.                 ++p;
  295.                                 /* "[^]" and "[]" are not the end of a range */
  296.             if (p[1] == '^')
  297.                 ++p;
  298.             if (p[1] == ']')
  299.                 ++p;
  300.         }
  301.         else if (p[0] == '\\' && p[1] != NUL)
  302.             ++p;    /* skip next character */
  303.         else if (p[0] == ']')
  304.             in_range = FALSE;
  305.     }
  306.     return p;
  307. }
  308.  
  309. /*
  310.  - regcomp - compile a regular expression into internal code
  311.  *
  312.  * We can't allocate space until we know how big the compiled form will be,
  313.  * but we can't compile it (and thus know how big it is) until we've got a
  314.  * place to put the code.  So we cheat:  we compile it twice, once with code
  315.  * generation turned off and size counting turned on, and once "for real".
  316.  * This also means that we don't allocate space until we are sure that the
  317.  * thing really will compile successfully, and we never have to move the
  318.  * code and thus invalidate pointers into it.  (Note that it has to be in
  319.  * one piece because free() must be able to free it all.)
  320.  *
  321.  * Beware that the optimization-preparation code in here knows about some
  322.  * of the structure of the compiled regexp.
  323.  */
  324.     regexp           *
  325. regcomp(exp)
  326.     char_u           *exp;
  327. {
  328.     register regexp *r;
  329.     register char_u  *scan;
  330.     register char_u  *longest;
  331.     register int    len;
  332.     int             flags;
  333. /*    extern char    *malloc();*/
  334.  
  335.     if (exp == NULL) {
  336.         EMSG_RETURN(e_null);
  337.     }
  338.  
  339. #ifdef EMPTY_RE            /* this is done outside of regexp */
  340.     if (*exp == '\0') {
  341.         if (reg_prev_re) {
  342.             exp = reg_prev_re;
  343.         } else {
  344.             EMSG_RETURN(e_noprevre);
  345.         }
  346.     }
  347. #endif
  348.  
  349.     /* First pass: determine size, legality. */
  350.     initchr((char_u *)exp);
  351.     regnpar = 1;
  352.     regsize = 0L;
  353.     regcode = ®dummy;
  354.     regendp = NULL;
  355.     regc(MAGIC);
  356.     if (reg(0, &flags) == NULL)
  357.         return NULL;
  358.  
  359.     /* Small enough for pointer-storage convention? */
  360.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  361.         EMSG_RETURN(e_toolong);
  362.  
  363.     /* Allocate space. */
  364. /*    r = (regexp *) malloc((unsigned) (sizeof(regexp) + regsize));*/
  365.     r = (regexp *) alloc((unsigned) (sizeof(regexp) + regsize));
  366.     if (r == NULL)
  367.         EMSG_RETURN(e_outofmem);
  368.  
  369. #ifdef EMPTY_RE            /* this is done outside of regexp */
  370.     if (exp != reg_prev_re) {
  371.         free(reg_prev_re);
  372.         if (reg_prev_re = alloc(STRLEN(exp) + 1))
  373.             STRCPY(reg_prev_re, exp);
  374.     }
  375. #endif
  376.  
  377.     /* Second pass: emit code. */
  378.     initchr((char_u *)exp);
  379.     regnpar = 1;
  380.     regcode = r->program;
  381.     regendp = r->endp;
  382.     regc(MAGIC);
  383.     if (reg(0, &flags) == NULL) {
  384.         free(r);
  385.         return NULL;
  386.     }
  387.  
  388.     /* Dig out information for optimizations. */
  389.     r->regstart = '\0';         /* Worst-case defaults. */
  390.     r->reganch = 0;
  391.     r->regmust = NULL;
  392.     r->regmlen = 0;
  393.     scan = r->program + 1;        /* First BRANCH. */
  394.     if (OP(regnext(scan)) == END) {     /* Only one top-level choice. */
  395.         scan = OPERAND(scan);
  396.  
  397.         /* Starting-point info. */
  398.         if (OP(scan) == EXACTLY)
  399.             r->regstart = *OPERAND(scan);
  400.         else if (OP(scan) == BOL)
  401.             r->reganch++;
  402.  
  403.         /*
  404.          * If there's something expensive in the r.e., find the longest
  405.          * literal string that must appear and make it the regmust.  Resolve
  406.          * ties in favor of later strings, since the regstart check works
  407.          * with the beginning of the r.e. and avoiding duplication
  408.          * strengthens checking.  Not a strong reason, but sufficient in the
  409.          * absence of others.
  410.          */
  411.         /*
  412.          * When the r.e. starts with BOW, it is faster to look for a regmust
  413.          * first. Used a lot for "#" and "*" commands. (Added by mool).
  414.          */
  415.         if (flags & SPSTART || OP(scan) == BOW) {
  416.             longest = NULL;
  417.             len = 0;
  418.             for (; scan != NULL; scan = regnext(scan))
  419.                 if (OP(scan) == EXACTLY && STRLEN(OPERAND(scan)) >= (size_t)len) {
  420.                     longest = OPERAND(scan);
  421.                     len = STRLEN(OPERAND(scan));
  422.                 }
  423.             r->regmust = longest;
  424.             r->regmlen = len;
  425.         }
  426.     }
  427. #ifdef DEBUG
  428.     regdump(r);
  429. #endif
  430.     return r;
  431. }
  432.  
  433. /*
  434.  - reg - regular expression, i.e. main body or parenthesized thing
  435.  *
  436.  * Caller must absorb opening parenthesis.
  437.  *
  438.  * Combining parenthesis handling with the base level of regular expression
  439.  * is a trifle forced, but the need to tie the tails of the branches to what
  440.  * follows makes it hard to avoid.
  441.  */
  442.     static char_u *
  443. reg(paren, flagp)
  444.     int             paren;        /* Parenthesized? */
  445.     int            *flagp;
  446. {
  447.     register char_u  *ret;
  448.     register char_u  *br;
  449.     register char_u  *ender;
  450.     register int    parno = 0;
  451.     int             flags;
  452.  
  453.     *flagp = HASWIDTH;            /* Tentatively. */
  454.  
  455.     /* Make an MOPEN node, if parenthesized. */
  456.     if (paren) {
  457.         if (regnpar >= NSUBEXP)
  458.             EMSG_RETURN(e_toombra);
  459.         parno = regnpar;
  460.         regnpar++;
  461.         ret = regnode(MOPEN + parno);
  462.         if (regendp)
  463.             regendp[parno] = NULL;    /* haven't seen the close paren yet */
  464.     } else
  465.         ret = NULL;
  466.  
  467.     /* Pick up the branches, linking them together. */
  468.     br = regbranch(&flags);
  469.     if (br == NULL)
  470.         return NULL;
  471.     if (ret != NULL)
  472.         regtail(ret, br);        /* MOPEN -> first. */
  473.     else
  474.         ret = br;
  475.     if (!(flags & HASWIDTH))
  476.         *flagp &= ~HASWIDTH;
  477.     *flagp |= flags & SPSTART;
  478.     while (peekchr() == Magic('|')) {
  479.         skipchr();
  480.         br = regbranch(&flags);
  481.         if (br == NULL)
  482.             return NULL;
  483.         regtail(ret, br);        /* BRANCH -> BRANCH. */
  484.         if (!(flags & HASWIDTH))
  485.             *flagp &= ~HASWIDTH;
  486.         *flagp |= flags & SPSTART;
  487.     }
  488.  
  489.     /* Make a closing node, and hook it on the end. */
  490.     ender = regnode((paren) ? MCLOSE + parno : END);
  491.     regtail(ret, ender);
  492.  
  493.     /* Hook the tails of the branches to the closing node. */
  494.     for (br = ret; br != NULL; br = regnext(br))
  495.         regoptail(br, ender);
  496.  
  497.     /* Check for proper termination. */
  498.     if (paren && getchr() != Magic(')')) {
  499.         EMSG_RETURN(e_toombra);
  500.     } else if (!paren && peekchr() != '\0') {
  501.         if (PeekChr() == Magic(')')) {
  502.             EMSG_RETURN(e_toomket);
  503.         } else
  504.             EMSG_RETURN(e_trailing);/* "Can't happen". */
  505.         /* NOTREACHED */
  506.     }
  507.     /*
  508.      * Here we set the flag allowing back references to this set of
  509.      * parentheses.
  510.      */
  511.     if (paren && regendp)
  512.         regendp[parno] = ender;    /* have seen the close paren */
  513.     return ret;
  514. }
  515.  
  516. /*
  517.  - regbranch - one alternative of an | operator
  518.  *
  519.  * Implements the concatenation operator.
  520.  */
  521.     static char_u    *
  522. regbranch(flagp)
  523.     int            *flagp;
  524. {
  525.     register char_u  *ret;
  526.     register char_u  *chain;
  527.     register char_u  *latest;
  528.     int             flags;
  529.  
  530.     *flagp = WORST;             /* Tentatively. */
  531.  
  532.     ret = regnode(BRANCH);
  533.     chain = NULL;
  534.     while (peekchr() != '\0' && PeekChr() != Magic('|') && PeekChr() != Magic(')')) {
  535.         latest = regpiece(&flags);
  536.         if (latest == NULL)
  537.             return NULL;
  538.         *flagp |= flags & HASWIDTH;
  539.         if (chain == NULL)        /* First piece. */
  540.             *flagp |= flags & SPSTART;
  541.         else
  542.             regtail(chain, latest);
  543.         chain = latest;
  544.     }
  545.     if (chain == NULL)            /* Loop ran zero times. */
  546.         (void) regnode(NOTHING);
  547.  
  548.     return ret;
  549. }
  550.  
  551. /*
  552.  - regpiece - something followed by possible [*+=]
  553.  *
  554.  * Note that the branching code sequences used for = and the general cases
  555.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  556.  * both the endmarker for their branch list and the body of the last branch.
  557.  * It might seem that this node could be dispensed with entirely, but the
  558.  * endmarker role is not redundant.
  559.  */
  560. static char_u    *
  561. regpiece(flagp)
  562.     int            *flagp;
  563. {
  564.     register char_u  *ret;
  565.     register int    op;
  566.     register char_u  *next;
  567.     int             flags;
  568.  
  569.     ret = regatom(&flags);
  570.     if (ret == NULL)
  571.         return NULL;
  572.  
  573.     op = peekchr();
  574.     if (!ismult(op)) {
  575.         *flagp = flags;
  576.         return ret;
  577.     }
  578.     if (!(flags & HASWIDTH) && op != Magic('='))
  579.         EMSG_RETURN((char_u *)"*+ operand could be empty");
  580.     *flagp = (op != Magic('+')) ? (WORST | SPSTART) : (WORST | HASWIDTH);
  581.  
  582.     if (op == Magic('*') && (flags & SIMPLE))
  583.         reginsert(STAR, ret);
  584.     else if (op == Magic('*')) {
  585.         /* Emit x* as (x&|), where & means "self". */
  586.         reginsert(BRANCH, ret); /* Either x */
  587.         regoptail(ret, regnode(BACK));    /* and loop */
  588.         regoptail(ret, ret);    /* back */
  589.         regtail(ret, regnode(BRANCH));    /* or */
  590.         regtail(ret, regnode(NOTHING)); /* null. */
  591.     } else if (op == Magic('+') && (flags & SIMPLE))
  592.         reginsert(PLUS, ret);
  593.     else if (op == Magic('+')) {
  594.         /* Emit x+ as x(&|), where & means "self". */
  595.         next = regnode(BRANCH); /* Either */
  596.         regtail(ret, next);
  597.         regtail(regnode(BACK), ret);    /* loop back */
  598.         regtail(next, regnode(BRANCH)); /* or */
  599.         regtail(ret, regnode(NOTHING)); /* null. */
  600.     } else if (op == Magic('=')) {
  601.         /* Emit x= as (x|) */
  602.         reginsert(BRANCH, ret); /* Either x */
  603.         regtail(ret, regnode(BRANCH));    /* or */
  604.         next = regnode(NOTHING);/* null. */
  605.         regtail(ret, next);
  606.         regoptail(ret, next);
  607.     }
  608.     skipchr();
  609.     if (ismult(peekchr()))
  610.         EMSG_RETURN((char_u *)"Nested *=+");
  611.  
  612.     return ret;
  613. }
  614.  
  615. /*
  616.  - regatom - the lowest level
  617.  *
  618.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  619.  * it can turn them into a single node, which is smaller to store and
  620.  * faster to run.
  621.  */
  622. static char_u    *
  623. regatom(flagp)
  624.     int            *flagp;
  625. {
  626.     register char_u  *ret;
  627.     int             flags;
  628.  
  629.     *flagp = WORST;             /* Tentatively. */
  630.  
  631.     switch (getchr()) {
  632.       case Magic('^'):
  633.         ret = regnode(BOL);
  634.         break;
  635.       case Magic('$'):
  636.         ret = regnode(EOL);
  637.         break;
  638.       case Magic('<'):
  639.         ret = regnode(BOW);
  640.         break;
  641.       case Magic('>'):
  642.         ret = regnode(EOW);
  643.         break;
  644.       case Magic('.'):
  645.         ret = regnode(ANY);
  646.         *flagp |= HASWIDTH | SIMPLE;
  647.         break;
  648.       case Magic('['):{
  649.             /*
  650.              * In a character class, different parsing rules apply.
  651.              * Not even \ is special anymore, nothing is.
  652.              */
  653.             if (*regparse == '^') {     /* Complement of range. */
  654.                 ret = regnode(ANYBUT);
  655.                 regparse++;
  656.             } else
  657.                 ret = regnode(ANYOF);
  658.             if (*regparse == ']' || *regparse == '-')
  659.                 regc(*regparse++);
  660.             while (*regparse != '\0' && *regparse != ']') {
  661.                 if (*regparse == '-') {
  662.                     regparse++;
  663.                     if (*regparse == ']' || *regparse == '\0')
  664.                         regc('-');
  665.                     else {
  666.                         register int    class;
  667.                         register int    classend;
  668.  
  669.                         class = UCHARAT(regparse - 2) + 1;
  670.                         classend = UCHARAT(regparse);
  671.                         if (class > classend + 1)
  672.                             EMSG_RETURN(e_invrange);
  673.                         for (; class <= classend; class++)
  674.                             regc(class);
  675.                         regparse++;
  676.                     }
  677.                 } else if (*regparse == '\\' && regparse[1]) {
  678.                     regparse++;
  679.                     regc(*regparse++);
  680.                 } else
  681.                     regc(*regparse++);
  682.             }
  683.             regc('\0');
  684.             if (*regparse != ']')
  685.                 EMSG_RETURN(e_toomsbra);
  686.             skipchr();            /* let's be friends with the lexer again */
  687.             *flagp |= HASWIDTH | SIMPLE;
  688.         }
  689.         break;
  690.       case Magic('('):
  691.         ret = reg(1, &flags);
  692.         if (ret == NULL)
  693.             return NULL;
  694.         *flagp |= flags & (HASWIDTH | SPSTART);
  695.         break;
  696.       case '\0':
  697.       case Magic('|'):
  698.       case Magic(')'):
  699.         EMSG_RETURN(e_internal);    /* Supposed to be caught earlier. */
  700.         /* break; Not Reached */
  701.       case Magic('='):
  702.       case Magic('+'):
  703.       case Magic('*'):
  704.         EMSG_RETURN((char_u *)"=+* follows nothing");
  705.         /* break; Not Reached */
  706. #ifdef TILDE
  707.       case Magic('~'):            /* previous substitute pattern */
  708.             if (reg_prev_sub) {
  709.                 register char_u *p;
  710.  
  711.                 ret = regnode(EXACTLY);
  712.                 p = reg_prev_sub;
  713.                 while (*p) {
  714.                     regc(*p++);
  715.                 }
  716.                 regc('\0');
  717.                 if (p - reg_prev_sub) {
  718.                     *flagp |= HASWIDTH;
  719.                     if ((p - reg_prev_sub) == 1)
  720.                         *flagp |= SIMPLE;
  721.                 }
  722.               } else
  723.                 EMSG_RETURN(e_nopresub);
  724.             break;
  725. #endif
  726. #ifdef BACKREF
  727.       case Magic('1'):
  728.       case Magic('2'):
  729.       case Magic('3'):
  730.       case Magic('4'):
  731.       case Magic('5'):
  732.       case Magic('6'):
  733.       case Magic('7'):
  734.       case Magic('8'):
  735.       case Magic('9'): {
  736.             int                refnum;
  737.  
  738.             ungetchr();
  739.             refnum = getchr() - Magic('0');
  740.             /*
  741.              * Check if the back reference is legal. We use the parentheses
  742.              * pointers to mark encountered close parentheses, but this
  743.              * is only available in the second pass. Checking opens is
  744.              * always possible.
  745.              * Should also check that we don't refer to something that
  746.              * is repeated (+*=): what instance of the repetition should
  747.              * we match? TODO.
  748.              */
  749.             if (refnum < regnpar &&
  750.                 (regendp == NULL || regendp[refnum] != NULL))
  751.                 ret = regnode(BACKREF + refnum);
  752.             else
  753.                 EMSG_RETURN((char_u *)"Illegal back reference");
  754.         }
  755.         break;
  756. #endif
  757.       default:{
  758.             register int    len;
  759.             int                chr;
  760.  
  761.             ungetchr();
  762.             len = 0;
  763.             ret = regnode(EXACTLY);
  764.             while ((chr = peekchr()) != '\0' && (chr < Magic(0)))
  765.             {
  766.                 regc(chr);
  767.                 skipchr();
  768.                 len++;
  769.             }
  770. #ifdef DEBUG
  771.             if (len == 0)
  772.                  EMSG_RETURN((char_u *)"Unexpected magic character; check META.");
  773. #endif
  774.             /*
  775.              * If there is a following *, \+ or \= we need the character
  776.              * in front of it as a single character operand
  777.              */
  778.             if (len > 1 && ismult(chr))
  779.             {
  780.                 unregc();            /* Back off of *+= operand */
  781.                 ungetchr();            /* and put it back for next time */
  782.                 --len;
  783.             }
  784.             regc('\0');
  785.             *flagp |= HASWIDTH;
  786.             if (len == 1)
  787.                 *flagp |= SIMPLE;
  788.         }
  789.         break;
  790.     }
  791.  
  792.     return ret;
  793. }
  794.  
  795. /*
  796.  - regnode - emit a node
  797.  */
  798. static char_u    *                /* Location. */
  799. regnode(op)
  800.     int            op;
  801. {
  802.     register char_u  *ret;
  803.     register char_u  *ptr;
  804.  
  805.     ret = regcode;
  806.     if (ret == ®dummy) {
  807.         regsize += 3;
  808.         return ret;
  809.     }
  810.     ptr = ret;
  811.     *ptr++ = op;
  812.     *ptr++ = '\0';                /* Null "next" pointer. */
  813.     *ptr++ = '\0';
  814.     regcode = ptr;
  815.  
  816.     return ret;
  817. }
  818.  
  819. /*
  820.  - regc - emit (if appropriate) a byte of code
  821.  */
  822. static void
  823. regc(b)
  824.     int            b;
  825. {
  826.     if (regcode != ®dummy)
  827.         *regcode++ = b;
  828.     else
  829.         regsize++;
  830. }
  831.  
  832. /*
  833.  - unregc - take back (if appropriate) a byte of code
  834.  */
  835. static void
  836. unregc()
  837. {
  838.     if (regcode != ®dummy)
  839.         regcode--;
  840.     else
  841.         regsize--;
  842. }
  843.  
  844. /*
  845.  - reginsert - insert an operator in front of already-emitted operand
  846.  *
  847.  * Means relocating the operand.
  848.  */
  849. static void
  850. reginsert(op, opnd)
  851.     int            op;
  852.     char_u           *opnd;
  853. {
  854.     register char_u  *src;
  855.     register char_u  *dst;
  856.     register char_u  *place;
  857.  
  858.     if (regcode == ®dummy) {
  859.         regsize += 3;
  860.         return;
  861.     }
  862.     src = regcode;
  863.     regcode += 3;
  864.     dst = regcode;
  865.     while (src > opnd)
  866.         *--dst = *--src;
  867.  
  868.     place = opnd;                /* Op node, where operand used to be. */
  869.     *place++ = op;
  870.     *place++ = '\0';
  871.     *place = '\0';
  872. }
  873.  
  874. /*
  875.  - regtail - set the next-pointer at the end of a node chain
  876.  */
  877. static void
  878. regtail(p, val)
  879.     char_u           *p;
  880.     char_u           *val;
  881. {
  882.     register char_u  *scan;
  883.     register char_u  *temp;
  884.     register int    offset;
  885.  
  886.     if (p == ®dummy)
  887.         return;
  888.  
  889.     /* Find last node. */
  890.     scan = p;
  891.     for (;;) {
  892.         temp = regnext(scan);
  893.         if (temp == NULL)
  894.             break;
  895.         scan = temp;
  896.     }
  897.  
  898.     if (OP(scan) == BACK)
  899.         offset = (int)(scan - val);
  900.     else
  901.         offset = (int)(val - scan);
  902.     *(scan + 1) = (char_u) ((offset >> 8) & 0377);
  903.     *(scan + 2) = (char_u) (offset & 0377);
  904. }
  905.  
  906. /*
  907.  - regoptail - regtail on operand of first argument; nop if operandless
  908.  */
  909. static void
  910. regoptail(p, val)
  911.     char_u           *p;
  912.     char_u           *val;
  913. {
  914.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  915.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  916.         return;
  917.     regtail(OPERAND(p), val);
  918. }
  919.  
  920. /*
  921.  - getchr() - get the next character from the pattern. We know about
  922.  * magic and such, so therefore we need a lexical analyzer.
  923.  */
  924.  
  925. /* static int        curchr; */
  926. static int        prevchr;
  927. static int        nextchr;    /* used for ungetchr() */
  928.  
  929. static void
  930. initchr(str)
  931. char_u *str;
  932. {
  933.     regparse = str;
  934.     curchr = prevchr = nextchr = -1;
  935. }
  936.  
  937. static int
  938. peekchr()
  939. {
  940.     if (curchr < 0) {
  941.         switch (curchr = regparse[0]) {
  942.         case '.':
  943.         case '*':
  944.     /*    case '+':*/
  945.     /*    case '=':*/
  946.         case '[':
  947.         case '~':
  948.             if (reg_magic)
  949.                 curchr = Magic(curchr);
  950.             break;
  951.         case '^':
  952.             /* ^ is only magic as the very first character */
  953.             if (prevchr < 0)
  954.                 curchr = Magic('^');
  955.             break;
  956.         case '$':
  957.             /* $ is only magic as the very last character and in front of '\|' */
  958.             if (regparse[1] == NUL || (regparse[1] == '\\' && regparse[2] == '|'))
  959.                 curchr = Magic('$');
  960.             break;
  961.         case '\\':
  962.             regparse++;
  963.             if (regparse[0] == NUL)
  964.                 curchr = '\\';    /* trailing '\' */
  965.             else if (STRCHR(META, regparse[0]))
  966.             {
  967.                 /*
  968.                  * META contains everything that may be magic sometimes, except
  969.                  * ^ and $ ("\^" and "\$" are never magic).
  970.                  * We now fetch the next character and toggle its magicness.
  971.                  * Therefore, \ is so meta-magic that it is not in META.
  972.                  */
  973.                 curchr = -1;
  974.                 peekchr();
  975.                 curchr ^= Magic(0);
  976.             }
  977.             else
  978.             {
  979.                 /*
  980.                  * Next character can never be (made) magic?
  981.                  * Then backslashing it won't do anything.
  982.                  */
  983.                 curchr = regparse[0];
  984.             }
  985.             break;
  986.         }
  987.     }
  988.  
  989.     return curchr;
  990. }
  991.  
  992. static void
  993. skipchr()
  994. {
  995.     regparse++;
  996.     prevchr = curchr;
  997.     curchr = nextchr;        /* use previously unget char, or -1 */
  998.     nextchr = -1;
  999. }
  1000.  
  1001. static int
  1002. getchr()
  1003. {
  1004.     int chr;
  1005.  
  1006.     chr = peekchr();
  1007.     skipchr();
  1008.  
  1009.     return chr;
  1010. }
  1011.  
  1012. /*
  1013.  * put character back. Works only once!
  1014.  */
  1015. static void
  1016. ungetchr()
  1017. {
  1018.     nextchr = curchr;
  1019.     curchr = prevchr;
  1020.     /*
  1021.      * Backup regparse as well; not because we will use what it points at,
  1022.      * but because skipchr() will bump it again.
  1023.      */
  1024.     regparse--;
  1025. }
  1026.  
  1027. /*
  1028.  * regexec and friends
  1029.  */
  1030.  
  1031. /*
  1032.  * Global work variables for regexec().
  1033.  */
  1034. static char_u    *reginput;        /* String-input pointer. */
  1035. static char_u    *regbol;         /* Beginning of input, for ^ check. */
  1036. static char_u   **regstartp;        /* Pointer to startp array. */
  1037. /* static char_u   **regendp;    */    /* Ditto for endp. */
  1038.  
  1039. /*
  1040.  * Forwards.
  1041.  */
  1042. static int        regtry __ARGS((regexp *, char_u *));
  1043. static int        regmatch __ARGS((char_u *));
  1044. static int        regrepeat __ARGS((char_u *));
  1045.  
  1046. #ifdef DEBUG
  1047. int             regnarrate = 1;
  1048. void            regdump __ARGS((regexp *));
  1049. static char_u    *regprop __ARGS((char_u *));
  1050. #endif
  1051.  
  1052. /*
  1053.  - regexec - match a regexp against a string
  1054.  */
  1055. int
  1056. regexec(prog, string, at_bol)
  1057.     register regexp *prog;
  1058.     register char_u  *string;
  1059.     int             at_bol;
  1060. {
  1061.     register char_u  *s;
  1062.  
  1063.     /* Be paranoid... */
  1064.     if (prog == NULL || string == NULL) {
  1065.         emsg(e_null);
  1066.         return 0;
  1067.     }
  1068.     /* Check validity of program. */
  1069.     if (UCHARAT(prog->program) != MAGIC) {
  1070.         emsg(e_re_corr);
  1071.         return 0;
  1072.     }
  1073.     /* If there is a "must appear" string, look for it. */
  1074.     if (prog->regmust != NULL) {
  1075.         s = string;
  1076.         while ((s = cstrchr(s, prog->regmust[0])) != NULL) {
  1077.             if (cstrncmp(s, prog->regmust, prog->regmlen) == 0)
  1078.                 break;            /* Found it. */
  1079.             s++;
  1080.         }
  1081.         if (s == NULL)            /* Not present. */
  1082.             return 0;
  1083.     }
  1084.     /* Mark beginning of line for ^ . */
  1085.     if (at_bol)
  1086.         regbol = string;        /* is possible to match bol */
  1087.     else
  1088.         regbol = NULL;            /* we aren't there, so don't match it */
  1089.  
  1090.     /* Simplest case:  anchored match need be tried only once. */
  1091.     if (prog->reganch)
  1092.         return regtry(prog, string);
  1093.  
  1094.     /* Messy cases:  unanchored match. */
  1095.     s = string;
  1096.     if (prog->regstart != '\0')
  1097.         /* We know what char it must start with. */
  1098.         while ((s = cstrchr(s, prog->regstart)) != NULL) {
  1099.             if (regtry(prog, s))
  1100.                 return 1;
  1101.             s++;
  1102.         }
  1103.     else
  1104.         /* We don't -- general case. */
  1105.         do {
  1106.             if (regtry(prog, s))
  1107.                 return 1;
  1108.         } while (*s++ != '\0');
  1109.  
  1110.     /* Failure. */
  1111.     return 0;
  1112. }
  1113.  
  1114. /*
  1115.  - regtry - try match at specific point
  1116.  */
  1117. static int                        /* 0 failure, 1 success */
  1118. regtry(prog, string)
  1119.     regexp           *prog;
  1120.     char_u           *string;
  1121. {
  1122.     register int    i;
  1123.     register char_u **sp;
  1124.     register char_u **ep;
  1125.  
  1126.     reginput = string;
  1127.     regstartp = prog->startp;
  1128.     regendp = prog->endp;
  1129.  
  1130.     sp = prog->startp;
  1131.     ep = prog->endp;
  1132.     for (i = NSUBEXP; i > 0; i--) {
  1133.         *sp++ = NULL;
  1134.         *ep++ = NULL;
  1135.     }
  1136.     if (regmatch(prog->program + 1)) {
  1137.         prog->startp[0] = string;
  1138.         prog->endp[0] = reginput;
  1139.         return 1;
  1140.     } else
  1141.         return 0;
  1142. }
  1143.  
  1144. /*
  1145.  - regmatch - main matching routine
  1146.  *
  1147.  * Conceptually the strategy is simple:  check to see whether the current
  1148.  * node matches, call self recursively to see whether the rest matches,
  1149.  * and then act accordingly.  In practice we make some effort to avoid
  1150.  * recursion, in particular by going through "ordinary" nodes (that don't
  1151.  * need to know whether the rest of the match failed) by a loop instead of
  1152.  * by recursion.
  1153.  */
  1154. static int                        /* 0 failure, 1 success */
  1155. regmatch(prog)
  1156.     char_u           *prog;
  1157. {
  1158.     register char_u  *scan;        /* Current node. */
  1159.     char_u           *next;        /* Next node. */
  1160.  
  1161.     scan = prog;
  1162. #ifdef DEBUG
  1163.     if (scan != NULL && regnarrate)
  1164.         fprintf(stderr, "%s(\n", regprop(scan));
  1165. #endif
  1166.     while (scan != NULL) {
  1167. #ifdef DEBUG
  1168.         if (regnarrate) {
  1169.             fprintf(stderr, "%s...\n", regprop(scan));
  1170.         }
  1171. #endif
  1172.         next = regnext(scan);
  1173.         switch (OP(scan)) {
  1174.           case BOL:
  1175.             if (reginput != regbol)
  1176.                 return 0;
  1177.             break;
  1178.           case EOL:
  1179.             if (*reginput != '\0')
  1180.                 return 0;
  1181.             break;
  1182.           case BOW:        /* \<word; reginput points to w */
  1183. #define isidchar(x)    (isalnum(x) || ((x) == '_'))
  1184.               if (reginput != regbol && isidchar(reginput[-1]))
  1185.                 return 0;
  1186.               if (!reginput[0] || !isidchar(reginput[0]))
  1187.                 return 0;
  1188.             break;
  1189.           case EOW:        /* word\>; reginput points after d */
  1190.               if (reginput == regbol || !isidchar(reginput[-1]))
  1191.                 return 0;
  1192.               if (reginput[0] && isidchar(reginput[0]))
  1193.                 return 0;
  1194.             break;
  1195.           case ANY:
  1196.             if (*reginput == '\0')
  1197.                 return 0;
  1198.             reginput++;
  1199.             break;
  1200.           case EXACTLY:{
  1201.                 register int    len;
  1202.                 register char_u  *opnd;
  1203.  
  1204.                 opnd = OPERAND(scan);
  1205.                 /* Inline the first character, for speed. */
  1206.                 if (*opnd != *reginput && (!reg_ic || TO_UPPER(*opnd) != TO_UPPER(*reginput)))
  1207.                     return 0;
  1208.                 len = STRLEN(opnd);
  1209.                 if (len > 1 && cstrncmp(opnd, reginput, len) != 0)
  1210.                     return 0;
  1211.                 reginput += len;
  1212.             }
  1213.             break;
  1214.           case ANYOF:
  1215.             if (*reginput == '\0' || cstrchr(OPERAND(scan), *reginput) == NULL)
  1216.                 return 0;
  1217.             reginput++;
  1218.             break;
  1219.           case ANYBUT:
  1220.             if (*reginput == '\0' || cstrchr(OPERAND(scan), *reginput) != NULL)
  1221.                 return 0;
  1222.             reginput++;
  1223.             break;
  1224.           case NOTHING:
  1225.             break;
  1226.           case BACK:
  1227.             break;
  1228.           case MOPEN + 1:
  1229.           case MOPEN + 2:
  1230.           case MOPEN + 3:
  1231.           case MOPEN + 4:
  1232.           case MOPEN + 5:
  1233.           case MOPEN + 6:
  1234.           case MOPEN + 7:
  1235.           case MOPEN + 8:
  1236.           case MOPEN + 9:{
  1237.                 register int    no;
  1238.                 register char_u  *save;
  1239.  
  1240.                 no = OP(scan) - MOPEN;
  1241.                 save = regstartp[no];
  1242.                 regstartp[no] = reginput; /* Tentatively */
  1243. #ifdef DEBUG
  1244.                 printf("MOPEN  %d pre  @'%s' ('%s' )'%s'\n",
  1245.                     no, save,
  1246.                     regstartp[no] ? regstartp[no] : "NULL",
  1247.                     regendp[no] ? regendp[no] : "NULL");
  1248. #endif
  1249.  
  1250.                 if (regmatch(next)) {
  1251. #ifdef DEBUG
  1252.                 printf("MOPEN  %d post @'%s' ('%s' )'%s'\n",
  1253.                     no, save,
  1254.                     regstartp[no] ? regstartp[no] : "NULL",
  1255.                     regendp[no] ? regendp[no] : "NULL");
  1256. #endif
  1257.                     return 1;
  1258.                 }
  1259.                 regstartp[no] = save;        /* We were wrong... */
  1260.                 return 0;
  1261.             }
  1262.             /* break; Not Reached */
  1263.           case MCLOSE + 1:
  1264.           case MCLOSE + 2:
  1265.           case MCLOSE + 3:
  1266.           case MCLOSE + 4:
  1267.           case MCLOSE + 5:
  1268.           case MCLOSE + 6:
  1269.           case MCLOSE + 7:
  1270.           case MCLOSE + 8:
  1271.           case MCLOSE + 9:{
  1272.                 register int    no;
  1273.                 register char_u  *save;
  1274.  
  1275.                 no = OP(scan) - MCLOSE;
  1276.                 save = regendp[no];
  1277.                 regendp[no] = reginput; /* Tentatively */
  1278. #ifdef DEBUG
  1279.                 printf("MCLOSE %d pre  @'%s' ('%s' )'%s'\n",
  1280.                     no, save,
  1281.                     regstartp[no] ? regstartp[no] : "NULL",
  1282.                     regendp[no] ? regendp[no] : "NULL");
  1283. #endif
  1284.  
  1285.                 if (regmatch(next)) {
  1286. #ifdef DEBUG
  1287.                 printf("MCLOSE %d post @'%s' ('%s' )'%s'\n",
  1288.                     no, save,
  1289.                     regstartp[no] ? regstartp[no] : "NULL",
  1290.                     regendp[no] ? regendp[no] : "NULL");
  1291. #endif
  1292.                     return 1;
  1293.                 }
  1294.                 regendp[no] = save;        /* We were wrong... */
  1295.                 return 0;
  1296.             }
  1297.             /* break; Not Reached */
  1298. #ifdef BACKREF
  1299.           case BACKREF + 1:
  1300.           case BACKREF + 2:
  1301.           case BACKREF + 3:
  1302.           case BACKREF + 4:
  1303.           case BACKREF + 5:
  1304.           case BACKREF + 6:
  1305.           case BACKREF + 7:
  1306.           case BACKREF + 8:
  1307.           case BACKREF + 9:{
  1308.                 register int    no;
  1309.                 int                len;
  1310.  
  1311.                 no = OP(scan) - BACKREF;
  1312.                 if (regendp[no] != NULL) {
  1313.                     len = (int)(regendp[no] - regstartp[no]);
  1314.                     if (cstrncmp(regstartp[no], reginput, len) != 0)
  1315.                         return 0;
  1316.                     reginput += len;
  1317.                 } else {
  1318.                     /*emsg("backref to 0-repeat");*/
  1319.                     /*return 0;*/
  1320.                 }
  1321.               }
  1322.             break;
  1323. #endif
  1324.           case BRANCH:{
  1325.                 register char_u  *save;
  1326.  
  1327.                 if (OP(next) != BRANCH) /* No choice. */
  1328.                     next = OPERAND(scan);        /* Avoid recursion. */
  1329.                 else {
  1330.                     do {
  1331.                         save = reginput;
  1332.                         if (regmatch(OPERAND(scan)))
  1333.                             return 1;
  1334.                         reginput = save;
  1335.                         scan = regnext(scan);
  1336.                     } while (scan != NULL && OP(scan) == BRANCH);
  1337.                     return 0;
  1338.                     /* NOTREACHED */
  1339.                 }
  1340.             }
  1341.             break;
  1342.           case STAR:
  1343.           case PLUS:{
  1344.                 register int    nextch;
  1345.                 register int    no;
  1346.                 register char_u  *save;
  1347.                 register int    min;
  1348.  
  1349.                 /*
  1350.                  * Lookahead to avoid useless match attempts when we know
  1351.                  * what character comes next.
  1352.                  */
  1353.                 nextch = '\0';
  1354.                 if (OP(next) == EXACTLY)
  1355.                 {
  1356.                     nextch = *OPERAND(next);
  1357.                     if (reg_ic)
  1358.                         nextch = TO_UPPER(nextch);
  1359.                 }
  1360.                 min = (OP(scan) == STAR) ? 0 : 1;
  1361.                 save = reginput;
  1362.                 no = regrepeat(OPERAND(scan));
  1363.                 while (no >= min)
  1364.                 {
  1365.                     /* If it could work, try it. */
  1366.                     if (nextch == '\0' || (*reginput == nextch ||
  1367.                                     (reg_ic && TO_UPPER(*reginput) == nextch)))
  1368.                         if (regmatch(next))
  1369.                             return 1;
  1370.                     /* Couldn't or didn't -- back up. */
  1371.                     no--;
  1372.                     reginput = save + no;
  1373.                 }
  1374.                 return 0;
  1375.             }
  1376.             /* break; Not Reached */
  1377.           case END:
  1378.             return 1;         /* Success! */
  1379.             /* break; Not Reached */
  1380.           default:
  1381.             emsg(e_re_corr);
  1382.             return 0;
  1383.             /* break; Not Reached */
  1384.         }
  1385.  
  1386.         scan = next;
  1387.     }
  1388.  
  1389.     /*
  1390.      * We get here only if there's trouble -- normally "case END" is the
  1391.      * terminating point.
  1392.      */
  1393.     emsg(e_re_corr);
  1394.     return 0;
  1395. }
  1396.  
  1397. /*
  1398.  - regrepeat - repeatedly match something simple, report how many
  1399.  */
  1400. static int
  1401. regrepeat(p)
  1402.     char_u           *p;
  1403. {
  1404.     register int    count = 0;
  1405.     register char_u  *scan;
  1406.     register char_u  *opnd;
  1407.  
  1408.     scan = reginput;
  1409.     opnd = OPERAND(p);
  1410.     switch (OP(p)) {
  1411.       case ANY:
  1412.         count = STRLEN(scan);
  1413.         scan += count;
  1414.         break;
  1415.       case EXACTLY:
  1416.         while (*opnd == *scan || (reg_ic && TO_UPPER(*opnd) == TO_UPPER(*scan)))
  1417.         {
  1418.             count++;
  1419.             scan++;
  1420.         }
  1421.         break;
  1422.       case ANYOF:
  1423.         while (*scan != '\0' && cstrchr(opnd, *scan) != NULL)
  1424.         {
  1425.             count++;
  1426.             scan++;
  1427.         }
  1428.         break;
  1429.       case ANYBUT:
  1430.         while (*scan != '\0' && cstrchr(opnd, *scan) == NULL) {
  1431.             count++;
  1432.             scan++;
  1433.         }
  1434.         break;
  1435.       default:                    /* Oh dear.  Called inappropriately. */
  1436.         emsg(e_re_corr);
  1437.         count = 0;                /* Best compromise. */
  1438.         break;
  1439.     }
  1440.     reginput = scan;
  1441.  
  1442.     return count;
  1443. }
  1444.  
  1445. /*
  1446.  - regnext - dig the "next" pointer out of a node
  1447.  */
  1448. static char_u    *
  1449. regnext(p)
  1450.     register char_u  *p;
  1451. {
  1452.     register int    offset;
  1453.  
  1454.     if (p == ®dummy)
  1455.         return NULL;
  1456.  
  1457.     offset = NEXT(p);
  1458.     if (offset == 0)
  1459.         return NULL;
  1460.  
  1461.     if (OP(p) == BACK)
  1462.         return p - offset;
  1463.     else
  1464.         return p + offset;
  1465. }
  1466.  
  1467. #ifdef DEBUG
  1468.  
  1469. /*
  1470.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1471.  */
  1472. void
  1473. regdump(r)
  1474.     regexp           *r;
  1475. {
  1476.     register char_u  *s;
  1477.     register int    op = EXACTLY;        /* Arbitrary non-END op. */
  1478.     register char_u  *next;
  1479.     /*extern char_u    *strchr();*/
  1480.  
  1481.  
  1482.     s = r->program + 1;
  1483.     while (op != END) {         /* While that wasn't END last time... */
  1484.         op = OP(s);
  1485.         printf("%2d%s", s - r->program, regprop(s));    /* Where, what. */
  1486.         next = regnext(s);
  1487.         if (next == NULL)        /* Next ptr. */
  1488.             printf("(0)");
  1489.         else
  1490.             printf("(%d)", (s - r->program) + (next - s));
  1491.         s += 3;
  1492.         if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1493.             /* Literal string, where present. */
  1494.             while (*s != '\0') {
  1495.                 putchar(*s);
  1496.                 s++;
  1497.             }
  1498.             s++;
  1499.         }
  1500.         putchar('\n');
  1501.     }
  1502.  
  1503.     /* Header fields of interest. */
  1504.     if (r->regstart != '\0')
  1505.         printf("start `%c' ", r->regstart);
  1506.     if (r->reganch)
  1507.         printf("anchored ");
  1508.     if (r->regmust != NULL)
  1509.         printf("must have \"%s\"", r->regmust);
  1510.     printf("\n");
  1511. }
  1512.  
  1513. /*
  1514.  - regprop - printable representation of opcode
  1515.  */
  1516. static char_u    *
  1517. regprop(op)
  1518.     char_u           *op;
  1519. {
  1520.     register char_u  *p;
  1521.     static char_u     buf[50];
  1522.  
  1523.     (void) strcpy(buf, ":");
  1524.  
  1525.     switch (OP(op)) {
  1526.       case BOL:
  1527.         p = "BOL";
  1528.         break;
  1529.       case EOL:
  1530.         p = "EOL";
  1531.         break;
  1532.       case ANY:
  1533.         p = "ANY";
  1534.         break;
  1535.       case ANYOF:
  1536.         p = "ANYOF";
  1537.         break;
  1538.       case ANYBUT:
  1539.         p = "ANYBUT";
  1540.         break;
  1541.       case BRANCH:
  1542.         p = "BRANCH";
  1543.         break;
  1544.       case EXACTLY:
  1545.         p = "EXACTLY";
  1546.         break;
  1547.       case NOTHING:
  1548.         p = "NOTHING";
  1549.         break;
  1550.       case BACK:
  1551.         p = "BACK";
  1552.         break;
  1553.       case END:
  1554.         p = "END";
  1555.         break;
  1556.       case MOPEN + 1:
  1557.       case MOPEN + 2:
  1558.       case MOPEN + 3:
  1559.       case MOPEN + 4:
  1560.       case MOPEN + 5:
  1561.       case MOPEN + 6:
  1562.       case MOPEN + 7:
  1563.       case MOPEN + 8:
  1564.       case MOPEN + 9:
  1565.         sprintf(buf + STRLEN(buf), "MOPEN%d", OP(op) - MOPEN);
  1566.         p = NULL;
  1567.         break;
  1568.       case MCLOSE + 1:
  1569.       case MCLOSE + 2:
  1570.       case MCLOSE + 3:
  1571.       case MCLOSE + 4:
  1572.       case MCLOSE + 5:
  1573.       case MCLOSE + 6:
  1574.       case MCLOSE + 7:
  1575.       case MCLOSE + 8:
  1576.       case MCLOSE + 9:
  1577.         sprintf(buf + STRLEN(buf), "MCLOSE%d", OP(op) - MCLOSE);
  1578.         p = NULL;
  1579.         break;
  1580.       case BACKREF + 1:
  1581.       case BACKREF + 2:
  1582.       case BACKREF + 3:
  1583.       case BACKREF + 4:
  1584.       case BACKREF + 5:
  1585.       case BACKREF + 6:
  1586.       case BACKREF + 7:
  1587.       case BACKREF + 8:
  1588.       case BACKREF + 9:
  1589.         sprintf(buf + STRLEN(buf), "BACKREF%d", OP(op) - BACKREF);
  1590.         p = NULL;
  1591.         break;
  1592.       case STAR:
  1593.         p = "STAR";
  1594.         break;
  1595.       case PLUS:
  1596.         p = "PLUS";
  1597.         break;
  1598.       default:
  1599.         sprintf(buf + STRLEN(buf), "corrupt %d", OP(op));
  1600.         p = NULL;
  1601.         break;
  1602.     }
  1603.     if (p != NULL)
  1604.         (void) strcat(buf, p);
  1605.     return buf;
  1606. }
  1607. #endif
  1608.  
  1609. /*
  1610.  * The following is provided for those people who do not have strcspn() in
  1611.  * their C libraries.  They should get off their butts and do something
  1612.  * about it; at least one public-domain implementation of those (highly
  1613.  * useful) string routines has been published on Usenet.
  1614.  */
  1615. #ifdef STRCSPN
  1616. /*
  1617.  * strcspn - find length of initial segment of s1 consisting entirely
  1618.  * of characters not from s2
  1619.  */
  1620.  
  1621. static int
  1622. strcspn(s1, s2)
  1623.     const char_u           *s1;
  1624.     const char_u           *s2;
  1625. {
  1626.     register char_u  *scan1;
  1627.     register char_u  *scan2;
  1628.     register int    count;
  1629.  
  1630.     count = 0;
  1631.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1632.         for (scan2 = s2; *scan2 != '\0';)        /* ++ moved down. */
  1633.             if (*scan1 == *scan2++)
  1634.                 return count;
  1635.         count++;
  1636.     }
  1637.     return count;
  1638. }
  1639. #endif
  1640.  
  1641. /*
  1642.  * Compare two strings, ignore case if reg_ic set.
  1643.  * Return 0 if strings match, non-zero otherwise.
  1644.  */
  1645.     int
  1646. cstrncmp(s1, s2, n)
  1647.     char_u           *s1, *s2;
  1648.     int             n;
  1649. {
  1650.     if (!reg_ic)
  1651.         return STRNCMP(s1, s2, (size_t)n);
  1652.  
  1653.     return vim_strnicmp(s1, s2, (size_t)n);
  1654. }
  1655.  
  1656. /*
  1657.  * cstrchr: This function is used a lot for simple searches, keep it fast!
  1658.  */
  1659.     char_u *
  1660. cstrchr(s, c)
  1661.     char_u           *s;
  1662.     register int    c;
  1663. {
  1664.     register char_u           *p;
  1665.  
  1666.     if (!reg_ic)
  1667.         return STRCHR(s, c);
  1668.  
  1669.     c = TO_UPPER(c);
  1670.  
  1671.     for (p = s; *p; p++)
  1672.     {
  1673.         if (TO_UPPER(*p) == c)
  1674.             return p;
  1675.     }
  1676.     return NULL;
  1677. }
  1678.